package leetcode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

//将无向无环图变成树，求树的高度最矮时的树的根节点
public class MinimumHeightTrees {

//	First let's review some statement for tree in graph theory:
//
//	(1) A tree is an undirected graph in which any two vertices are
//	connected by exactly one path.
//
//	(2) Any connected graph who has n nodes with n-1 edges is a tree.
//
//	(3) The degree of a vertex of a graph is the number of
//	edges incident to the vertex.
//
//	(4) A leaf is a vertex of degree 1. An internal vertex is a vertex of
//	degree at least 2.
//
	//这个我也有一点不理解
	//Wikipedia： a path graph or linear graph is a graph whose vertices can be listed in the order v1, v2, …, vn
//	(5) A path graph is a tree with two or more vertices that is not
//	branched at all.
//
//	(6) A tree is called a rooted tree if one vertex has been designated
//	the root.
//
//	(7) The height of a rooted tree is the number of edges on the longest
//	downward path between root and a leaf.
	
	//OK. Let's stop here and look at our problem.

//	Our problem want us to find the minimum height trees and return their root labels. 
//		First we can think about a simple case -- a path graph.

//	For a path graph of n nodes, find the minimum height trees is trivial. 
//	Just designate the middle point(s) as roots.

	//Despite its triviality, let design a algorithm to find them.

	//Suppose we don't know n, nor do we have random access of the nodes. We have to traversal. 
	//It is very easy to get the idea of two pointers. One from each end and move at the same speed. 
	// When they meet or they are one step away, (depends on the parity of n), we have the roots we want.

	//This gives us a lot of useful ideas to crack our real problem.

	//For a tree we can do some thing similar.We start from every end, by end we mean vertex of degree 1(leaves). 
	// We let the pointers move the same speed. When two pointers meet, we keep only one of them, 
	// until the last two pointers meet or one step away we then find the roots.

	//It is easy to see that the last two pointers are from the two ends of the longest path in the graph.

	// The actual implementation is similar to the BFS topological sort. Remove the leaves, 
	//update the degrees of inner vertexes. Then remove the new leaves. 
	//Doing so level by level until there are 2 or 1 nodes left. What's left is our answer!

	//The time complexity and space complexity are both O(n).

    //Note that for a tree we always have V = n, E = n-1.
	
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
    	
    	//如果没有边，直接返回0即可
    	if(n == 1){
    		ArrayList<Integer> list = new ArrayList<>();
    		list.add(0);
    		return list;
    	}
    	List<Set<Integer>> list = new ArrayList<>();
    	for (int i = 0; i < n; ++i) {
    		list.add(new HashSet<Integer>());
    	}
    	//维护一个边到边的映射
    	for (int[] edge : edges) {
    		list.get(edge[0]).add(edge[1]);
    		list.get(edge[1]).add(edge[0]);
    	}
    	
    	//记录所有的叶子节点
    	List<Integer> leaves = new ArrayList<>();
        for (int i = 0; i < n; ++i)
            if (list.get(i).size() == 1) leaves.add(i);
        
        while(n > 2){
        	n -= leaves.size();
        	List<Integer> newLeaves = new ArrayList<>();
        	for(int i : leaves){
        		//找到叶子节点的相邻结点
        		int j = list.get(i).iterator().next();
        		
        		//避免i -> j, j -> i这种重复
        		list.get(j).remove(i);
        		
        		//成为新的叶子节点
        		if (list.get(j).size() == 1) newLeaves.add(j);
        	}
        	leaves = newLeaves;
        }
        return leaves;
    }
}
